package l.l.w.CodingInterviews;

/**
 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
 * 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
 * 在本题中，匹配是指字符串的所有字符匹配整个模式。
 * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 */
public class 正则表达式匹配 {
    public boolean match(char[] str, char[] pattern){
        if(str == null || pattern == null) return false;
        return isMatch(str, 0, pattern, 0);
    }

    private boolean isMatch(char[] str, int i, char[] pattern, int j){
        //如果原串和匹配串均结束，则说明匹配成功
        if(i == str.length && j == pattern.length){
            return true;
        }
        //若原串还未结束，但是 模式串已经结束，则说明 不匹配
        if(i < str.length && j == pattern.length){
            return false;
        }
        /*如果模式串的下一个字符为  '*'，则查看当前对应的字符是否匹配：
        *   若匹配：则分三种情况
        *       模式后移2，视为x*匹配0个字符
        *       *匹配1个，再匹配str中的下一个
        *       视为模式匹配1个字符
        *   若不匹配：则模式串的当前 字符和* 需要跳过，然后匹配下一个字符
        * */
        if(j + 1 < pattern.length && pattern[j + 1] == '*'){
            if(i < str.length && (str[i] == pattern[j] || pattern[j] == '.')){
                return isMatch(str, i, pattern, j + 2)
                        || isMatch(str, i + 1, pattern, j)
                        || isMatch(str, i + 1, pattern, j + 2);
            }
            return isMatch(str, i, pattern, j + 2);
        }
        if(i < str.length && (str[i] == pattern[j] || pattern[j] == '.')){
            return isMatch(str, i + 1, pattern, j + 1);
        }
        return false;
    }

    public static void main(String[] args) {
        String str = "";
        String pattern = ".*";
        boolean result = new 正则表达式匹配().match(str.toCharArray(), pattern.toCharArray());
        System.out.println(result);
    }
}
